# leetcode 239 滑动窗口最大值
# 难度：困难
# 时间复杂度：O(n)


#方法：优先队列,堆

from typing import List
import heapq

class Solution:

    #leetcode官方题解
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        # 注意 Python 默认的优先队列是小根堆
        q = [(-nums[i], i) for i in range(k)]
        heapq.heapify(q)

        ans = [-q[0][0]]
        for i in range(k, n):
            heapq.heappush(q, (-nums[i], i))
            while q[0][1] <= i - k:
                heapq.heappop(q)
            ans.append(-q[0][0])
        
        return ans

    #解法来自第三个视频，由java转成python而来。
    #TODO



# 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
# 输出：[3,3,5,5,6,7]
# 解释：
# 滑动窗口的位置                最大值
# ---------------               -----
# [1  3  -1] -3  5  3  6  7       3
#  1 [3  -1  -3] 5  3  6  7       3
#  1  3 [-1  -3  5] 3  6  7       5
#  1  3  -1 [-3  5  3] 6  7       5
#  1  3  -1  -3 [5  3  6] 7       6
#  1  3  -1  -3  5 [3  6  7]      7


nums = [1,3,-1,-3,5,3,6,7]
k = 3
#预期输出：[3,3,5,5,6,7]
solution = Solution()
print(solution.maxSlidingWindow(nums, k))


nums = [1]
k = 1
#预期输出：[1]
solution = Solution()
print(solution.maxSlidingWindow(nums, k))